package _interview75;

/**
 * 208. 实现 Trie (前缀树)
 */
public class No208 {
    private final TrieNode root;

    public No208() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode curNode = root;
        for (char c : word.toCharArray()) {
            if (curNode.child[c - 'a'] == null) curNode.child[c - 'a'] = new TrieNode();
            curNode = curNode.child[c - 'a'];
        }
        curNode.isValid = true;
    }

    public boolean search(String word) {
        TrieNode curNode = root;
        for (char c : word.toCharArray()) {
            if (curNode.child[c - 'a'] == null) return false;
            curNode = curNode.child[c - 'a'];
        }
        return curNode.isValid;
    }

    public boolean startsWith(String prefix) {
        TrieNode curNode = root;
        for (char c : prefix.toCharArray()) {
            if (curNode.child[c - 'a'] == null) return false;
            curNode = curNode.child[c - 'a'];
        }
        return true;
    }

    private static class TrieNode {
        private final TrieNode[] child;
        private boolean isValid;

        private TrieNode() {
            child = new TrieNode[26];
        }
    }
}
